package com.gaogzhen.introductiontoalgorithms3.divideconquer;

import cn.hutool.core.util.ArrayUtil;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 求解最大子数组
 * @author gaogzhen
 * @date 2024/5/12 11:06
 */
public class MaxSubarray {

    public  static Map<String, Integer>   maxSubarray(Integer[] arr, int low, int high) {
        if (high == low) {
            Map<String, Integer> ret = new HashMap<>(3);
            ret.put("low", low);
            ret.put("high", high);
            ret.put("sum", arr[low]);
            return ret;
        } else {
            int mid = (low + high) /2;
            Map<String, Integer> mapLeft = maxSubarray(arr, low, mid);
            Map<String, Integer> mapRight = maxSubarray(arr, mid + 1, high);
            Map<String, Integer> mapCross = maxCrossSubarray(arr, low, mid, high);
            Integer sumLeft = mapLeft.get("sum");
            Integer sumRight = mapRight.get("sum");
            Integer sumCross = mapCross.get("sum");

            if (sumLeft >= sumRight && sumLeft >= sumCross) {
                return mapLeft;
            } else if (sumRight >= sumLeft && sumRight >= sumCross) {
                return mapRight;
            } else {
                return mapCross;
            }
        }
    }

    private static Map<String, Integer> maxCrossSubarray(Integer[] arr, int low, int mid, int high) {
        int sumLeft = Integer.MIN_VALUE;
        int indexLeft = 0;
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += arr[i];
            if (sum > sumLeft) {
                sumLeft = sum;
                indexLeft = i;
            }
        }
        sum = 0;
        int sumRight = Integer.MIN_VALUE;
        int indexRight = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum += arr[i];
            if (sum > sumRight) {
                sumRight = sum;
                indexRight = i;
            }
        }
        Map<String, Integer> map = new HashMap<>(3);
        map.put("low", indexLeft);
        map.put("high", indexRight);
        map.put("sum", sumLeft + sumRight);
        return map;
    }

    public static void main(String[] args) {
        // Integer[] arr = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
        Integer[] arr = {-13, -3, -25, -20, -3, -16, -23, -18, -20, -1, -12, -5, -22, -15, -4, -7};
        Map<String, Integer> map = maxSubarray(arr, 0, arr.length - 1);
        Integer low = map.get("low");
        Integer high = map.get("high");
        Integer[] sub = ArrayUtil.sub(arr, low, high + 1);
        System.out.println(Arrays.toString(sub));
        System.out.println(map);
    }
}
